package 排序;

import 排序.tools.Integers;

public class BubbleSort<E extends Comparable<E>> extends Sort<E>{
	public static void main(String[] args) {
		Integer[] array = Integers.random(20, 1, 50);
		Integers.println(array);
		bubbleSort(array);
		Integers.println(array);
	}
	
	public static void bubbleSort(Integer[] array) {
		for (int end = array.length - 1; end > 0; end--) {
			for (int begin = 1; begin <= end; begin++) {
				if (array[begin] < array[begin - 1]) {
					int tmp = array[begin];
					array[begin] = array[begin - 1];
					array[begin - 1] = tmp;
				}
			}
		}
	}
	
	/**
	 * 优化一: 已排序, 可提前终止排序
	 * @param array
	 */
	public static void bubbleSort1(Integer[] array) {
		for (int end = array.length - 1; end > 0; end--) {
			boolean sorted = true;	// 默认排序
			for (int begin = 1; begin <= end; begin++) {
				if (array[begin] < array[begin - 1]) {
					int tmp = array[begin];
					array[begin] = array[begin - 1];
					array[begin - 1] = tmp;
					sorted = false;
				}
			}
			if (sorted) break;
		}
	}
	
	/**
	 * 优化二: 尾部局部排序, 记录最后一次交换的位置, 减少排序次数
	 * @param array
	 */
	public static void bubbleSort2(Integer[] array) {
		for (int end = array.length - 1; end > 0; end--) {
			int sortedIndex = 1;	// 记录最后一次交换的位置
			for (int begin = 1; begin <= end; begin++) {
				if (array[begin] < array[begin - 1]) {
					int tmp = array[begin];
					array[begin] = array[begin - 1];
					array[begin - 1] = tmp;
					sortedIndex = begin;
				}
			}
			end = sortedIndex;
		}
	}

	@Override
	protected void sort() {
		for (int end = array.length - 1; end > 0; end--) {
			int sortedIndex = 1;
			for (int begin = 1; begin <= end; begin++) {
				if (cmp(begin, begin - 1) < 0) {
					swap(begin, begin - 1);
					sortedIndex = begin;
				}
			}
			end = sortedIndex;
		}
	}
}
